package comparable

type pair struct {
	l int
	r int
}

type pair32 struct {
	l int32
	r int32
}

type Seq []pair
type Seq32 []pair32

func (s Seq) Len() int32 {
	return int32(len(s))
}

func (s Seq32) Len() int32 {
	return int32(len(s))
}

type Comparable interface {
	Less(b Comparable) bool
}

type ComparableList interface {
	Len() int32
	ILoc(a int32) Comparable
}

func LowerBound(seq ComparableList, v Comparable) int32 {
	L := int32(0)
	R := seq.Len() - 1
	if R < 0 || seq.ILoc(R).Less(v) {
		return R + 1
	}
	for L < R {
		mid := L + (R-L)>>1
		if seq.ILoc(mid).Less(v) {
			L = mid + 1
		} else {
			R = mid
		}
	}
	return R
}

func UpperBound(seq ComparableList, v Comparable) int32 {
	L := int32(0)
	R := seq.Len() - 1
	if R < 0 || seq.ILoc(R).Less(v) || !v.Less(seq.ILoc(R)) {
		return R + 1
	}
	for L < R {
		mid := L + (R-L)>>1
		if seq.ILoc(mid).Less(v) || !v.Less(seq.ILoc(mid)) {
			L = mid + 1
		} else {
			R = mid
		}
	}
	return R
}

func LowerBoundInt(seq []int, v int) int32 {
	L := int32(0)
	R := int32(len(seq)) - 1
	if R < 0 || seq[R] < v {
		return R + 1
	}
	for L < R {
		mid := L + (R-L)>>1
		if seq[mid] < v {
			L = mid + 1
		} else {
			R = mid
		}
	}
	return R
}

func UpperBoundInt(seq []int, v int) int32 {
	L := int32(0)
	R := int32(len(seq)) - 1
	if R < 0 || seq[R] <= v {
		return R + 1
	}
	for L < R {
		mid := L + (R-L)>>1
		if seq[mid] <= v {
			L = mid + 1
		} else {
			R = mid
		}
	}
	return R
}

func LowerBound32(seq []int32, v int32) int32 {
	L := int32(0)
	R := int32(len(seq)) - 1
	if R < 0 || seq[R] < v {
		return R + 1
	}
	for L < R {
		mid := L + (R-L)>>1
		if seq[mid] < v {
			L = mid + 1
		} else {
			R = mid
		}
	}
	return R
}

func UpperBound32(seq []int32, v int32) int32 {
	L := int32(0)
	R := int32(len(seq)) - 1
	if R < 0 || seq[R] <= v {
		return R + 1
	}
	for L < R {
		mid := L + (R-L)>>1
		if seq[mid] <= v {
			L = mid + 1
		} else {
			R = mid
		}
	}
	return R
}
